Computers typically contain a bus, which may be a set of hardware lines or conductors used for information transfer between the various components of the computer system, such as the processor, the memory, and the input/output ports. A bus typically consists of specialized groups of lines that carry different types of information. For example, one group of lines might carry data, while another group of lines carries memory addresses where the data can be found, and still another group carries control signals. Some computers contain multiple buses, for example a system bus and an I/O (input/output) bus. These multiple buses might not have the same number of lines, and the lines might have different meanings. Thus, at the point where these multiple buses connect with each other, specialized hardware is needed to convert the interface of one bus into the interface of another bus. This specialized hardware is often contained within a chip or chips.
The chips used in such a bus interface often receive many different types of commands. Typically, these commands are placed into separate queues in order to maximize throughput, so that if a first queue that services commands of a first type is full, a second queue can still accept and make progress executing commands of a second type. With this approach, there are occasions where commands in the various queues need to be ordered with respect to each other to prevent unintentional out-of-order execution.
Ordering commands in queues has been accomplished by designing logic that searches through the queues looking for command dependencies and sets hold-off bits in a register to indicate that a particular command is dependent on another command or commands already in one of the queues and cannot proceed until the previously accepted command or commands complete. A common problem in designs of this type is that the rules for which commands are dependent upon each other are fluid and change late in the design cycle of the chip. Additionally, design flaws on either end of the bus interface may necessitate different hold-off conditions than the designer originally contemplated. Unfortunately, the logic that searches the queues and determines command dependencies cannot be changed without redesigning the chip. Thus, there is a need for a solution that allows flexibility in ordering commands in queues.
Although the aforementioned problems have been described in the context of a chip in a bus interface, they can apply in any context where commands on command queues need to be ordered with respect to dependencies that they might have on each other.